Regular Expressions and Automata

For any nondeterministic finite acceptor (nfa) we can find an equivalent dfa. Thus nfas also describe regular languages.

Regular expressions also describe regular languages. We will show that regular expressions are equivalent to nfas by doing two things:

1. For any given regular expression, we will show how to build an nfa that accepts the same language. (This is the easy part.)

2. For any given nfa, we will show how to construct a regular expression that describes the same language. (This is the hard part.)